/*
 * @Author: nexox 2685853507@qq.com
 * @Date: 2024-11-25 20:37:10
 * @LastEditors: nexox 2685853507@qq.com
 * @LastEditTime: 2024-11-26 08:31:06
 * @FilePath: \pytorch_workplace\WorkPlace\oi\leetcode980.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @Author: nexox 2685853507@qq.com
 * @Date: 2024-11-25 20:37:10
 * @LastEditors: nexox 2685853507@qq.com
 * @LastEditTime: 2024-11-25 21:12:54
 * @FilePath: \pytorch_workplace\WorkPlace\oi\leetcode980.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <bitset>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
  private:
    vector<vector<bool>> visit;
    int rst;
    int n;
    int m;
    int sx, sy;
    int ex, ey;
    int ans;

  public:
    void dfs(vector<vector<int>> &grid, int x, int y, int cnt) {
        if (x < 0 || x >= n || y < 0 || y >= m) return;
        if (grid[x][y] == -1) return;
        if (grid[x][y] != 2 && cnt == 0) return;
        if (grid[x][y] == 2 && cnt != 0) return;
        if (grid[x][y] == 2 && cnt == 0) {
            ans++;
            return;
        }

        int sta = grid[x][y];
        grid[x][y] = -1;
        dfs(grid, x - 1, y, cnt - 1);
        dfs(grid, x + 1, y, cnt - 1);
        dfs(grid, x, y + 1, cnt - 1);
        dfs(grid, x, y - 1, cnt - 1);
        grid[x][y] = sta;
    }
    int uniquePathsIII(vector<vector<int>> &grid) {
        n = grid.size();
        m = grid[0].size();
        rst = n * m;
        ans = 0;
        sx = sy = ex = ey = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                rst -= (grid[i][j] == -1);
                if (grid[i][j] == 1) {
                    sx = i;
                    sy = j;
                } else if (grid[i][j] == 2) {
                    ex = i;
                    ey = j;
                }
            }
        }
        // cout<<ex<<" "<<ey<<endl;
        dfs(grid, sx, sy, rst - 1);
        return ans;
    }
};

int main() {
    vector<vector<int>> inp{{1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 2}};
    Solution sol;
    cout << sol.uniquePathsIII(inp);
}